import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @作者 钟先崟
 * @时间 2023-02-20 19:13
 * @说明 890. 查找和替换模式
 * 你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。
 * 如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
 * （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
 * 返回 words 中与给定模式匹配的单词列表。
 * 你可以按任何顺序返回答案。
 * 示例：
 * 输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
 * 输出：["mee","aqq"]
 * 解释：
 * "mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
 * "ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
 * 因为 a 和 b 映射到同一个字母。
 */
public class Solution {
    public static void main(String[] args) {
//        String[] words = new String[]{"abc", "deq", "mee", "aqq", "dkd", "ccc"};
//        String patten = "abb";
        String[] words = new String[]{"abc", "cba", "xyx", "yxx", "yyx"};
        String patten = "abc";
        List<String> andReplacePattern = findAndReplacePattern(words, patten);
        for (String str :
                andReplacePattern) {
            System.out.print(str + " ");
        }
    }

    /**
     * 执行用时：
     * 2 ms
     * , 在所有 Java 提交中击败了
     * 40.27%
     * 的用户
     * 内存消耗：
     * 40.3 MB
     * , 在所有 Java 提交中击败了
     * 91.95%
     * 的用户
     * @param words
     * @param pattern
     * @return
     */
    public static List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new ArrayList<>();
        int[] recordTheSubscript = new int[pattern.length()];
        Map<Character, Integer> map = new HashMap<>();
        Integer n;
        for (int i = 0; i < pattern.length(); i++) {
            n = map.get(pattern.charAt(i));
            if (n == null) {
                map.put(pattern.charAt(i), i);
                recordTheSubscript[i] = i;
            } else {
                recordTheSubscript[i] = n;
            }
        }
        int m = map.size();
        boolean isOK;
        for (String str : words) {
            isOK = true;
            map.clear();
            for (int i = 0; i < str.length(); i++) {
                n = map.get(str.charAt(i));
                if (n == null) {
                    map.put(str.charAt(i), i);
                } else {
                    if (!(recordTheSubscript[i] == n)) {
                        isOK = false;
                        break;
                    }
                }
            }
            if (map.size() != m) isOK = false;
            if (isOK) list.add(str);
        }
        return list;
    }
}
